package Leetcode;

import base.TreeNode;

import java.util.*;

/**
 * 给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
 */
public class 力扣103_二叉树的锯齿形层序遍历 {
    public static void main(String[] args) {
        TreeNode a = new TreeNode(1);
        TreeNode b = new TreeNode(2);
        TreeNode c = new TreeNode(3);
        TreeNode d = new TreeNode(4);
        TreeNode e = new TreeNode(5);
        TreeNode f = new TreeNode(6);
        TreeNode g = new TreeNode(7);

        a.left = b;
        a.right = c;
        b.left = d;
        b.right = e;
        c.left = f;
        c.right = g;

        List<List<Integer>> lists = zigzagLevelOrder(a);
        System.out.println(lists);
    }

    /**
     * 广度优先遍历
     * 和层次遍历的区别在于 需要根据每次的顺序 判断插入数组的顺序
     */
    public static List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        if (root == null) {
            return Collections.emptyList();
        }

        List<List<Integer>> result = new ArrayList<>();
        boolean asc = true;
        Deque<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            LinkedList<Integer> list = new LinkedList<>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode treeNode = queue.pollFirst();
                if (treeNode.left != null) {
                    queue.addLast(treeNode.left);
                }
                if (treeNode.right != null) {
                    queue.addLast(treeNode.right);
                }
                if (asc) {
                    list.addFirst(treeNode.val);
                } else {
                    list.addLast(treeNode.val);
                }
            }
            asc = !asc;
            result.add(list);
        }
        return result;
    }

    /**
     * 自己写的 和上边的区别在于  根据顺序  判断从队列中获取的先后和插入顺序
     */
    public static List<List<Integer>> zigzagLevelOrder1(TreeNode root) {
        if (root == null) {
            return Collections.emptyList();
        }
        List<List<Integer>> result = new ArrayList<>();
        boolean order = true;
        Deque<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            List<Integer> list = new ArrayList<>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                if (order) {
                    TreeNode first = queue.pollFirst();
                    list.add(first.val);
                    if (first.left != null) {
                        queue.addLast(first.left);
                    }
                    if (first.right != null) {
                        queue.addLast(first.right);
                    }
                } else {
                    TreeNode last = queue.pollLast();
                    list.add(last.val);
                    if (last.right != null) {
                        queue.addFirst(last.right);
                    }
                    if (last.left != null) {
                        queue.addFirst(last.left);
                    }
                }
            }
            order = !order;
            result.add(list);
        }

        return result;
    }

}
